#include "llvm/Pass.h"
#include "llvm/Module.h"
#include "llvm/Function.h"
#include "llvm/Instruction.h"
#include "llvm/Instructions.h"
#include "llvm/Constant.h"
#include "llvm/User.h"
#include "llvm/Value.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/InstIterator.h"
#include "llvm/Support/IRBuilder.h"
#include "llvm/Support/CFG.h"
#include "llvm/ExecutionEngine/ExecutionEngine.h"
#include "llvm/LLVMContext.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include <vector>
#include <map>
#include <list>
#include <string>


using namespace llvm;

int name_count = 0;

void reverse(char *a)
{
 int length = strlen(a);
 int b = 0, e = length - 1;
 while (b < e)
 {
  char temp = a[b];
  a[b] = a[e];
  a[e] = temp;
  b++;
  e--;
 }
}

void integerToString(int j, char *a)
{
 int p = 0;
 int q, r;
 
 while ((q = j/10) > 0)
  {
    r = j%10;
    a[p++] = r - 48;
    j = q;
  }
 r = j%10;
 //errs() << "in function " << r << "\n";
 a[p++] = r + 48;
 a[p] = '\0';
 //errs() << "in function " << a << "\n";

 reverse(a);

 //errs() << "in function " << a << "\n";


 return;
}

namespace
{

  struct eSSAPass1 : public FunctionPass {
        static char ID;
      eSSAPass1() : FunctionPass(ID) {}
      //void eSSAPass1::printInst(Instruction *inst);
    virtual bool runOnFunction(Function &F) {
      //errs() << "eSSAPass: " << F.getName() << "\n";
      IRBuilder<> *builder; //Used for creating PI functions thru PHI instructions

      for (inst_iterator i = inst_begin(F), E = inst_end(F); i != E; ++i)
      {
        Instruction *inst = &*i;

        if(inst->getOpcode()==Instruction::ICmp) {
          CmpInst::Predicate inequalityCond = ((ICmpInst*)inst)->getSignedPredicate();
          if((inequalityCond == CmpInst::ICMP_SLE) || (inequalityCond == CmpInst::ICMP_SLT)){

            User::op_iterator opIt = inst->op_begin();
            User::op_iterator opStart = opIt;
            Value *toBeReplaced;
            BasicBlock *bbParent=inst->getParent();
            //const char *insertedCheckIdentifier = "boundsCheck";
            //const char *instStringIdentifier = dyn_cast<const char*>(&*inst);
            //errs() << *bbParent << "\n";
            //errs() << "inst is" << *inst << "\n";
            std::list<BasicBlock *> b_list;
            for(succ_iterator SI=succ_begin(bbParent), SE=succ_end(bbParent);SI!=SE;SI++){
              BasicBlock *piTarget = *SI;
              b_list.push_back(piTarget);
            }
            std::list<BasicBlock *>::iterator l_it;
            for(l_it = b_list.begin(); l_it != b_list.end(); l_it++)
            {
              BasicBlock *piTarget = *l_it;
              toBeReplaced = opIt->get();

              if (isa<LoadInst>(toBeReplaced))
                continue;
              BasicBlock *def_block = ((Instruction *)toBeReplaced)->getParent();
              if(!def_block)
                errs() << "def block was null\n";
              builder = new IRBuilder<>(def_block);
              BasicBlock::iterator insertPointInSuccBlk_alloca = def_block->begin();
              for(;(&(*insertPointInSuccBlk_alloca)) != toBeReplaced; insertPointInSuccBlk_alloca++);
              do {
                insertPointInSuccBlk_alloca++;
              }while(isa<PHINode>(insertPointInSuccBlk_alloca));
              //  insertPointInSuccBlk_alloca++;
              builder->SetInsertPoint(def_block, *insertPointInSuccBlk_alloca);

              AllocaInst *newAlloca = builder->CreateAlloca(toBeReplaced->getType(), toBeReplaced, "myalloca");
              std::list<Instruction *> u_list;
              for(Value::use_iterator u_it = toBeReplaced->use_begin(); u_it != toBeReplaced->use_end(); u_it++)
              {
                
                Instruction * user_inst = (Instruction *)((u_it.getUse()).getUser());
                u_list.push_back(user_inst);
              }

              for(std::list<Instruction *>::iterator ulist_iter = u_list.begin(); ulist_iter != u_list.end(); ulist_iter++)
               {
                Instruction *user_inst;
                user_inst = *ulist_iter;
                if(isa<AllocaInst>(user_inst))
                  continue;

                builder = new IRBuilder<>(user_inst->getParent(), user_inst);
                builder->SetInsertPoint(def_block, *insertPointInSuccBlk_alloca);
                LoadInst* loadInst = builder->CreateLoad(newAlloca, "tempAlloca");

                user_inst->replaceUsesOfWith(toBeReplaced, loadInst);
              }
              //toBeReplaced->replaceAllUsesWith(newAlloca);
              delete builder;


              if(piTarget->getSinglePredecessor())
              {
                builder = new IRBuilder<>(piTarget);
                BasicBlock::iterator insertPointInSuccBlk = piTarget->begin();
                builder->SetInsertPoint(piTarget, *insertPointInSuccBlk);
                while(isa<PHINode>(insertPointInSuccBlk_alloca));
                StoreInst* stInst1 = builder->CreateStore(toBeReplaced, newAlloca);

                opIt++;
                toBeReplaced=opIt->get();


                if((!isa<ConstantInt>(toBeReplaced))/*||(cast<Value>("boundsCheck")(*inst)==inst)*/){
                  builder = new IRBuilder<>(piTarget);
                  builder->SetInsertPoint(piTarget, *insertPointInSuccBlk);
                  StoreInst* stInst2 = builder->CreateStore(toBeReplaced, newAlloca);

                }
                opIt = opStart;
              }
              else
              {
                //errs() << "was in else\n";
                BasicBlock *newBB = llvm::SplitEdge(bbParent, piTarget, this);
                //errs() << "after here\n";
                builder = new IRBuilder<>(newBB);
                //errs() << "after herei1\n";
                //errs() << *newBB << "\n";

                BasicBlock::iterator insertPointInSuccBlk = newBB->begin();
                builder->SetInsertPoint(newBB, *insertPointInSuccBlk);
                StoreInst* stInst1 = builder->CreateStore(toBeReplaced, newAlloca);

                opIt++;
                toBeReplaced=opIt->get();
                if (!isa<ConstantInt>(toBeReplaced)) {
                  builder->SetInsertPoint(newBB, *insertPointInSuccBlk);
                  StoreInst* stInst2 = builder->CreateStore(toBeReplaced, newAlloca);
                }
                opIt = opStart;
              }
            }
          }
        }
      }

      for (Function::iterator blk = F.begin(), lastBlk = F.end(); blk != lastBlk; ++blk) {
        //errs() << *blk << "\n";
      }

      return true;
    }
  };

    static void printInst(Instruction *inst)
    {
	errs() << *inst << "\n";
    }
  char eSSAPass1::ID = 0;
  static RegisterPass<eSSAPass1> X("eSSAPass1", "Extending SSA to eSSA in ABCD algorithm", false, false);
}
